|
In graph theory, the halved cube graph or half cube graph of order ''n'' is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph. ==Equivalent constructions== The construction of the halved cube graph can be reformulated in terms of binary numbers. The vertices of a hypercube may be labeled by binary numbers in such a way that two vertices are adjacent exactly when they differ in a single bit. The demicube may be constructed from the hypercube as the convex hull of the subset of binary numbers with an even number of nonzero bits (the evil numbers), and its edges connect pairs of numbers whose Hamming distance is exactly two.〔.〕 It is also possible to construct the halved cube graph from a lower-order hypercube graph, without taking a subset of the vertices: : where the superscript 2 denotes the square of the hypercube graph ''Q''''n'' − 1, the graph formed by connecting pairs of vertices whose distance is at most two in the original graph. For instance, the halved cube graph of order four may be formed from an ordinary three-dimensional cube by keeping the cube edges and adding edges connecting pairs of vertices that are on opposite corners of the same square face. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Halved cube graph」の詳細全文を読む スポンサード リンク
|